/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓α␈↓ αNEXOTIC AND EVEN PATHOLOGICAL CONTINUOUS FUNCTIONALS

␈↓ ↓H␈↓␈↓ α_The fixed point theory of recursive functions is based on continuous functionals such as

␈↓ ↓H␈↓1)␈↓ α8  ␈↓↓λf λx.(␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ f h x)␈↓.

␈↓ ↓H␈↓␈↓ α_The␈α∞theory␈α∞tells␈α∞us␈α∞that␈α∞each␈α∞continuous␈α∞monotonic␈α∞functional␈α∞has␈α∞a␈α∞fixed␈α∞point,␈α∞and␈α
we
␈↓ ↓H␈↓study␈αthe␈αfixed␈α
points␈αof␈αthose␈α
functionals␈αinvolved␈αin␈α
recursive␈αdefinitions.␈α However,␈α
these␈αare
␈↓ ↓H␈↓not␈αall␈α
the␈αcontinuous␈αfunctions␈α
there␈αare,␈αand␈α
it␈αmay␈α
be␈αinteresting␈αto␈α
study␈αsome␈αother␈α
examples.
␈↓ ↓H␈↓Consider functionals of the form

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓␈↓	t␈↓↓[f](x) = ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ m f␈↓∧ -1␈↓↓ h x␈↓;

␈↓ ↓H␈↓that's␈αright,␈αwe␈αmean␈αthe␈αinverse␈αof␈αthe␈αfunction␈α␈↓↓f␈↓.␈α In␈αorder␈αto␈αmake␈αthe␈αfunctional␈αwell␈αdefined
␈↓ ↓H␈↓and␈α∩continuous,␈α∩we␈α∩make␈α∩the␈α∩following␈α∩stipulations:␈α∩ First,␈α∩the␈α∩variable␈α∩␈↓↓x␈↓␈α∩ranges␈α∩over␈α⊃non-
␈↓ ↓H␈↓negative integers and ␈↓↓f␈↓ is a partial function from integers to integers.  We define ␈↓↓f␈↓∧ -1␈↓↓␈↓ by

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓f␈↓∧ -1␈↓↓(y) = ␈↓	m␈↓↓ x.(f(x) = y)␈↓,

␈↓ ↓H␈↓where

␈↓ ↓H␈↓4)␈↓ α8  ␈↓↓␈↓	m␈↓↓ x.p(x) ← least(0,p)␈↓,

␈↓ ↓H␈↓and ␈↓↓least(y,p)␈↓ is recursively defined by

␈↓ ↓H␈↓5)␈↓ α8  ␈↓↓least(y,p) ← ␈↓αif␈↓↓ p(y) ␈↓αthen␈↓↓ y ␈↓αelse␈↓↓ least(y+1,p)␈↓.

␈↓ ↓H␈↓Note␈α∩that␈α∩the␈α∩recursive␈α⊃definition␈α∩insures␈α∩that␈α∩␈↓↓f␈↓∧␈α⊃-1␈↓↓␈↓␈α∩is␈α∩continuous␈α∩in␈α⊃␈↓↓f,␈↓␈α∩and␈α∩that␈α∩␈↓	m␈↓x.␈↓↓p(x)␈↓␈α⊃is
␈↓ ↓H␈↓undefined␈α
if␈α
there␈α
is␈α
a␈α
value␈α
of␈α
␈↓↓x␈↓␈α
for␈α
which␈α
␈↓↓p(x)␈↓␈α
is␈α
undefined␈α
lower␈α
than␈α
a␈α
value␈α
for␈α
which␈α
␈↓↓p(x)␈↓␈α
is
␈↓ ↓H␈↓true.␈α Without␈αthis␈αproperty,␈α␈↓↓least(x,p)␈↓␈αwouldn't␈αbe␈αmonotonic␈αin␈α␈↓↓p␈↓,␈αand␈αthere␈αmightn't␈αbe␈αa␈αleast
␈↓ ↓H␈↓fixed point.

␈↓ ↓H␈↓␈↓ α_Consider specializing (2) to

␈↓ ↓H␈↓6)␈↓ α8  ␈↓↓␈↓	t␈↓↓1[f](x) = ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 2 + f␈↓∧ -1␈↓↓(x - 1)␈↓.

␈↓ ↓H␈↓The fixed point ␈↓↓f1␈↓ of ␈↓	t␈↓1 may be computed by iterating ␈↓	t␈↓1 on ␈↓	W␈↓, and the result seems to be

␈↓ ↓H␈↓7)␈↓ α8  ␈↓↓f1 x = ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x = 1 ␈↓αthen␈↓↓ 2 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x = 3 ␈↓αthen␈↓↓ 3 ␈↓αelse␈↓↓ ␈↓	w␈↓↓␈↓,

␈↓ ↓H␈↓and this seems exotic if not pathological.  We need to examine some more examples.

␈↓ ↓H␈↓Note:␈α⊂Wolf␈α⊂Polak␈α⊂points␈α⊂out␈α⊃that␈α⊂while␈α⊂␈↓	t␈↓1␈α⊂is␈α⊂exotic,␈α⊃its␈α⊂fixed␈α⊂point␈α⊂is␈α⊂an␈α⊃ordinary␈α⊂recursive
␈↓ ↓H␈↓function since the recursive computation of ␈↓↓f␈↓∧ -1␈↓↓␈↓ can be spelled out.  Thus

␈↓ ↓H␈↓8)␈↓ α8  ␈↓↓f1 x ← ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 2 + f2(0,x-1)␈↓,

␈↓ ↓H␈↓where

␈↓ ↓H␈↓9)␈↓ α8  ␈↓↓f2(y,x) ← ␈↓αif␈↓↓ f1(x) = y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ f2(y+1,x)␈↓.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ α_Here is another weird functional:

␈↓ ↓H␈↓10)␈↓ α8 ␈↓↓␈↓	t␈↓↓2[f](x) = ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ f h1 x = ␈↓	w␈↓↓ ∧ f h2 x = ␈↓	w␈↓↓ ␈↓αthen␈↓↓ ␈↓	w␈↓↓ ␈↓αelse␈↓↓ f h3 x␈↓,

␈↓ ↓H␈↓where␈α␈↓↓p,␈↓␈α␈↓↓g,␈↓␈α␈↓↓h1,␈↓␈α␈↓↓h2␈↓␈αand␈α␈↓↓h3␈↓␈αare␈αall␈αassumed␈αtotal.␈α Computing␈αit␈αinvolves␈αa␈αparallel␈αcomputation
␈↓ ↓H␈↓of␈α⊂␈↓↓f␈α∂h1␈α⊂x␈↓␈α∂and␈α⊂␈↓↓f␈α∂h2␈α⊂x␈↓;␈α∂if␈α⊂either␈α∂succeeds,␈α⊂the␈α∂other␈α⊂can␈α∂be␈α⊂stopped.␈α∂ It␈α⊂is␈α∂easily␈α⊂seen␈α⊂that␈α∂the
␈↓ ↓H␈↓functional␈αis␈αcontinuous␈αand␈α
hence␈αhas␈αa␈αfixed␈αpoint␈α
-␈αcall␈αit␈α␈↓↓f2.␈↓␈αIf␈α
we␈αcan␈αuse␈αLisp␈αfunctions,␈α
we
␈↓ ↓H␈↓can write an ordinary recursive definition of ␈↓↓f2,␈↓ namely

␈↓ ↓H␈↓11)␈↓ α8 ␈↓↓f2 x ← ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ (λy. f2 h3 x)(f2'(list(x),␈↓NIL␈↓↓))␈↓,

␈↓ ↓H␈↓with

␈↓ ↓H␈↓12)␈↓ α8␈α␈↓↓f2'(u,v)␈α←␈α␈↓αif␈↓↓␈α␈↓αn␈↓↓␈αu␈α␈↓αthen␈↓↓␈α(␈↓αn␈↓↓␈αv␈α∨␈αf2(v,␈↓NIL␈↓↓))␈α␈↓αelse␈↓↓␈αp␈αh1␈α␈↓αa␈↓↓␈αu␈α∨␈αp␈αh2␈α␈↓αa␈↓↓␈αu␈α∨␈αf2'(␈↓αd␈↓↓␈αu,␈αh1␈α␈↓αa␈↓↓␈αu␈α.
␈↓ ↓H␈↓↓(h2 ␈↓αa␈↓↓ u . v))␈↓.

␈↓ ↓H␈↓If␈αwe␈αare␈αnot␈αallowed␈αto␈αuse␈αLisp␈αfunctions,␈αthen␈α␈↓↓f2␈↓␈αmay␈αbe␈αone␈αof␈αHewitt's␈αand␈αPaterson's␈α(197x)
␈↓ ↓H␈↓examples of functions that can be written with parallel programs but not with recursive programs.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of EXOTIC[W77,JMC] PUBbed at 18:12 on March 10, 1977.␈↓